package jianzhi

type MedianFinder struct {
	nums []int
}

/** initialize your data structure here. */
func Constructor() MedianFinder {
	return MedianFinder{
		nums: []int{},
	}
}

func (this *MedianFinder) AddNum(num int) {
	if len(this.nums) == 0 || num >= this.nums[len(this.nums)-1] {
		this.nums = append(this.nums, num)
		return
	} else if num <= this.nums[0] {
		this.nums = append([]int{num}, this.nums...)
		return
	}

	var i int

	for i = 0; i < len(this.nums)-1; i++ {
		if this.nums[i] == num {
			break
		}

		if this.nums[i] < num && num < this.nums[i+1] {
			break
		}
	}

	temp := append([]int(nil), this.nums[:i+1]...)
	temp = append(temp, num)
	temp = append(temp, this.nums[i+1:]...)
	this.nums = temp

}

func (this *MedianFinder) FindMedian() float64 {

	len := len(this.nums)

	if len == 0 {
		return -1
	}

	if len%2 == 1 {
		return float64(this.nums[len/2])
	}

	var mid int = len / 2

	res := float64((this.nums[mid] + this.nums[mid-1])) / 2
	return res

}
